const Stack = require("./stack").Stack;

class BinarySearchTree {
    constructor(array) {
        this.top = null;

        if (array && array.length) {
            array.forEach(i =>{
                this.add(i);
            })
        }
    }

    add(val) {
        if (!this.top) {
            this.top = new TreeNode(val);
        } else {
            let node = this.top;

            while (node) {
                if (val > node.val) {
                    if (node.right) {
                        node = node.right;
                    } else {
                        node.right = new TreeNode(val);
                        return;
                    }
                } else if (val < node.val) {
                    if (node.left) {
                        node = node.left;
                    } else {
                        node.left = new TreeNode(val);
                        return;
                    }
                } else {
                    break;
                }
            }
        }
    }

    traverseDFS(fn, type) {
        this.deep(this.top, type);
    }

    deep(node, type) {
        if (type === "inOrder") {
            if (node.left) {
                this.deep(node.left, type);
            }
            console.log(node.val);

            if (node.right) {
                this.deep(node.right, type);
            }

        } else if (type === "preOrder") {
            console.log(node.val);

            if (node.left) {
                this.deep(node.left, type);
            }
            if (node.right) {
                this.deep(node.right, type);
            }
        } else if (type === "postOrder") {
            if (node.left) {
                this.deep(node.left, type);
            }

            if (node.right) {
                this.deep(node.right, type);
            }

            console.log(node.val);
        }
    }

    traverseBFS(fn) {
        let nodes = [this.top];
        while (nodes.length) {
            let tempNode = [];
            nodes.forEach(n => {
                fn(n);
                if (n.left) {
                    tempNode.push(n.left);
                }
                if (n.right) {
                    tempNode.push(n.right);
                }
            });
            nodes = tempNode;
        }
    }

    getMin() {
        let node = this.top;

        while (node) {
            if (node.left) {
                node = node.left
            } else {
                return node.val
            }
        }
    }

    getMax() {
        let node = this.top;

        while (node) {
            if (node.right) {
                node = node.right
            } else {
                return node.val
            }
        }
    }

    contains(val) {
        let node = this.top;
        while (node) {
            if (val === node.val) {
                return true;
            }
            if (val < node.val) {
                node = node.left;
            } else {
                node = node.right;
            }
        }

        return false;
    }

    getHeight() {
        let height = -1;
        let nodes = [this.top];
        while (nodes.length) {
            let tempNode = [];
            nodes.forEach(n => {
                if (n.left) {
                    tempNode.push(n.left);
                }
                if (n.right) {
                    tempNode.push(n.right);
                }
            });
            height ++;
            nodes = tempNode;
        }

        return height;
    }

    isBalanced() {
        let heightCount = 1;
        let nodes = [this.top];
        while (nodes.length) {

            let tempNode = [];
            nodes.forEach(n => {
                if (n.left) {
                    tempNode.push(n.left);
                }
                if (n.right) {
                    tempNode.push(n.right);
                }
            });
            if (nodes.length !== heightCount && tempNode.length !== 0) {
                return false;
            }
            heightCount *= 2;
            nodes = tempNode;

        }

        return true;
    }

    remove(val) {
        let node = this.top;
        let pre = this.top;
        while (node.length) {
            if (node.val < val) {
                pre = node;
                node = node.right;
            } else if (node.val > val) {
                pre = node;
                node = node.left;
            } else {
                if (node.left && node.right) {

                } else {
                    if (node.left) {

                    }
                }
            }
        }
    }

    isBalancedOptimized() {

    }

    print() {
        let str = "";
        let nodes = [this.top];
        while (nodes.length) {
            let tempNode = [];
            nodes.forEach(n => {
                str += n.val + " ";
                if (n.left) {
                    tempNode.push(n.left);
                }
                if (n.right) {
                    tempNode.push(n.right);
                }
            });
            str += "|";
            nodes = tempNode;
        }
        console.log(str);
    }

    printByLevel() {
        let str = "";
        let nodes = [this.top];
        while (nodes.length) {
            let tempNode = [];
            nodes.forEach(n => {
                str += n.val + " ";
                if (n.left) {
                    tempNode.push(n.left);
                }
                if (n.right) {
                    tempNode.push(n.right);
                }
            });
            str += "\n";
            nodes = tempNode;
        }
        console.log(str);
    }
}

class TreeNode {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

exports.BinarySearchTree = BinarySearchTree;